AlgoWiki

Class representative

Say we have a set of elements $X$, as well as an equivalence relation defined on $X$. The equivalence relation partitions the elements of $X$ into a set of equivalence classes. A '''class representative''' is a distinguished element of a class, and each equivalence class should have a unique representative.

A common problem is to count the number of equivalence classes. If class representatives are picked in a careful manner, it may often be relatively easy to count the number of distinct class representatives, and thus the number of equivalence classes.

Another application where class representatives appear is in the Union-find data structure. There the roots of the underlying trees can be considered as the representatives of their classes.

Problems